/**
 * 3. 无重复字符的最长子串
 *
 * 【中等】
 *
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 *
 * 示例 1:
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 示例 3:
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 			请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */

/**
 *
 * 使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标
 * 使用 j 来标记无重复子串开始下标，i 为当前遍历字符下标
 * 遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 j 为相同字符的下一位置，此时从 j 到 i 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中
 * 最后，返回 max 即可
 */
function lengthOfLongestSubstring(s: string): number {
	const map = new Map()
	let max = 0
	let j = 0
	for (let i = 0; j < s.length; i++) {
		if (map.has(s[i])) {
			// 更新 j 的位置
			j = Math.max(j, map.get(s[i]) + 1)
		}
		max = Math.max(max, i - j + 1)
		map.set(s[i], i)
	}

	return max
}
